package leetcode.editor.cn.dsa07_doublepointer;
//给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
//
// 示例 1: 
//
// 输入: 1->1->2
//输出: 1->2
// 
//
// 示例 2: 
//
// 输入: 1->1->2->3->3
//输出: 1->2->3 
// Related Topics 链表 
// 👍 433 👎 0

public class RemoveDuplicatesFromSortedList83 {
    public static void main(String[] args) {
        RemoveDuplicatesFromSortedList83 obj =
                new RemoveDuplicatesFromSortedList83();
        Solution solution = obj.new Solution();
        ListNode head = obj.new ListNode(-1);
        //int[] arr = {1,1,2};
        int[] arr = {1,1,2,3,3};
        //int[] arr = {1,2,3,4,5};
        ListNode node = head;
        for (int num : arr) {
            ListNode newNode = obj.new ListNode(num);
            node.next = newNode;
            node = node.next;
        }
        ListNode listNode = solution.deleteDuplicates(head.next);
        while (listNode != null) {
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
        System.out.print("NULL");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    class Solution {
        /**
         * 和删除数组重复元素处理思想是一致的，都是用双指针
         * 只不过数组是把不重复元素前移
         * 而链表则是直接删除重复元素
         */
        public ListNode deleteDuplicates(ListNode head) {
            // 处理边界
            if (head == null || head.next == null) return head;
            // 定义两个指针分别指向目标位和待移动元素位
            ListNode prevNode = head;
            ListNode node = head.next;
            while (node != null) {
                // 比较两个指针的值
                ListNode target = node;
                // 先移到下一个元素，因为当前元素可能会被删除
                node = node.next;
                if (target.val == prevNode.val) {
                    // 相等，则将当前位置元素删除
                    prevNode.next = target.next;
                    target.next = null;
                } else {
                    // 不相等，则把目标位置后移
                    prevNode = target;
                }
            }
            return head;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}